package com.kevin.Code.DP;

import scala.Int;

import javax.xml.bind.annotation.XmlInlineBinaryData;
import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * @author Vinlee Xiao
 * @Classname BestTimetoBuyandSellStockiv
 * @Description Leetcode 188 买卖股票的最佳时机lv 动态规划 中等难度
 * @Date 2021/10/11 21:19
 * @Version 1.0
 */
public class BestTimetoBuyandSellStockiv {

    /**
     * @param k
     * @param prices
     * @return
     */
    public int maxProfit(int k, int[] prices) {


        int len = prices.length;
        int minValue = Integer.MIN_VALUE / 2;

        if (k == 0 || len == 0) {
            return 0;
        }
        int[][][] dp = new int[len][2][k + 1];

        //初始化
        //0次不持有股票
        dp[0][0][0] = 0;
        //0次持有股票且交易股票为0 相当于当天买入股票
        dp[0][1][0] = -prices[0];
        int res = 0;
        //0天持有股票且交易了至少一次 不可能
        for (int i = 1; i <= k; i++) {
            dp[0][1][i] = minValue;
            dp[0][0][i] = minValue;
        }


        for (int i = 1; i < len; i++) {

            //第i天不持有股票 且没有交易过
            dp[i][0][0] = 0;

            //当天结束持有股票，之前没有卖过股票 1.当天买的，且之前不持有股票，且没有卖出过股票 2.之前就持有股票，且没有卖过股票
            dp[i][1][0] = Math.max(dp[i - 1][0][0] - prices[i], dp[i - 1][1][0]);
            for (int j = 1; j < k; j++) {

                //i天结束后不持有股票，且已经卖出了j次股票 1.当天结束后把股票卖了 2.前一天结束之后就不持有股票了，且已经卖了j次股票
                dp[i][0][j] = Math.max(dp[i - 1][1][j - 1] + prices[i], dp[i - 1][0][j]);
                //i天结束后持有股票且已经卖出了k次股票 1.当天买的，  2.前一天结束之后就持有了
                dp[i][1][j] = Math.max(dp[i - 1][0][j] - prices[i], dp[i - 1][1][j]);

            }
            //第i天结束后，不持有股票，且已经交易了k次 1.当天卖出了 2.前一天卖出了
            dp[i][0][k] = Math.max(dp[i - 1][1][k - 1] + prices[i], dp[i - 1][0][k]);
            //不能持有股票
            dp[i][1][k] = minValue;

        }


        for (int i = 1; i <= k; i++) {
//            System.out.println(dp[len - 1][0][i]);
            res = Math.max(res, Math.max(dp[len - 1][0][i], dp[len - 1][0][i - 1]));
        }

        return res;
    }

    public static void main(String[] args) {
        BestTimetoBuyandSellStockiv bestTimetoBuyandSellStockiv = new BestTimetoBuyandSellStockiv();
        int k = 1;
        int[] nums = new int[]{1, 2};
        int i = bestTimetoBuyandSellStockiv.maxProfit(k, nums);
        System.out.println(i);
    }
}
